#include <cstdio>
#include <cstring>
/*
    三维树状数组
    ===========
    BIT3d< T：计数变量的类型, D1:第一维的上限值, D2, D3 >
    query_sum(x, y, z): O(log(D1)log(D2)log(D3))
        立方体 (1,1,1) -> (x,y,z) 的和。
    add_value(x, y, z, v): O(log(D1)log(D2)log(D3))
        (x,y,z)处的值加v。
    ===========
    注意：x,y,z 要大于0。（为0会死循环，TE）
*/
template<typename T, int D1, int D2, int D3>
struct BIT3d{
	T a[D1][D2][D3];

    BIT3d(){ clear(); }
    inline void clear() { memset(a,0,sizeof(a)); }

    inline int lowbit(int x) { return x & (-x); }
	inline T query_sum(int x, int y, int z){
		assert(x > 0 && y > 0 && z > 0);
        T ans = 0;
		for (int i = x; i; i -= lowbit(i))
			for (int j = y; j; j -= lowbit(j))
				for (int k = z; k; k -= lowbit(k))
                    ans += a[i][j][k];
		return ans;
	}
	inline void add_value(int x, int y, int z, int v){
        assert(x > 0 && y > 0 && z > 0);
		for (int i = x; i < D1; i += lowbit(i))
			for (int j = y; j < D2; j += lowbit(j))
				for (int k = z; k < D3; k += lowbit(k))
                    a[i][j][k] += v;
	}
};

int main() {
    BIT3d<int,10,10,10> a;
    printf("[%d]\n", a.query_sum(2, 2, 2));
    a.add_value(2, 2, 2, 1);
    printf("[%d]\n", a.query_sum(2, 2, 2));
    printf("[%d]\n", a.query_sum(2, 2, 3));
    printf("[%d]\n", a.query_sum(2, 2, 1));
    return 0;
}